#pragma once

#include "types.hpp"
#include "hash/hash.hpp"
#include "hash/hashstatistic.hpp"
#include "stdlib/exception.hpp"
using namespace JHCPP::stdlib::jhException;
#include <map>
#include <vector>
#include <algorithm>

namespace JHCPP
{
	namespace hash
	{
		template <class Value, class HashFunc = Hash<Value>>
		class TLinearHashTable
		{
		public:
			typedef Value               ValueType;
			typedef Value&              Reference;
			typedef const Value&        ConstReference;
			typedef Value*              Pointer;
			typedef const Value*        ConstPointer;
			typedef HashFunc            Hash;
			typedef std::vector<Value>  Bucket;
			typedef std::vector<Bucket> BucketVec;
			typedef typename Bucket::iterator    BucketIterator;
			typedef typename BucketVec::iterator BucketVecIterator;

			class ConstIterator: public std::iterator<std::forward_iterator_tag, Value>
			{
			public:
				ConstIterator()
				{
				}

				ConstIterator(const BucketVecIterator& vecIt, const BucketVecIterator& endIt, const BucketIterator& buckIt):
				m_vecIt(vecIt),
				m_endIt(endIt),
				m_buckIt(buckIt)
				{
				}

				ConstIterator(const ConstIterator& it):
				m_vecIt(it.m_vecIt),
				m_endIt(it.m_endIt),
				m_buckIt(it.m_buckIt)
				{
				}

				ConstIterator& operator = (const ConstIterator& it)
				{
					ConstIterator tmp(it);
					swap(tmp);
					return *this;
				}

				void swap(ConstIterator& it)
				{
					using std::swap;
					swap(m_vecIt, it.m_vecIt);
					swap(m_endIt, it.m_endIt);
					swap(m_buckIt, it.m_buckIt);
				}

				bool operator == (const ConstIterator& it) const
				{
					return m_vecIt == it.m_vecIt && (m_vecIt == m_endIt || m_buckIt == it.m_buckIt);
				}

				bool operator != (const ConstIterator& it) const
				{
					return m_vecIt != it.m_vecIt || (m_vecIt != m_endIt && m_buckIt != it.m_buckIt);
				}

				const typename Bucket::value_type& operator * () const
				{
					return *m_buckIt;
				}

				const typename Bucket::value_type* operator -> () const
				{
					return &*m_buckIt;
				}

				ConstIterator& operator ++ () // prefix
				{
					if (m_vecIt != m_endIt)
					{
						++m_buckIt;
						while (m_vecIt != m_endIt && m_buckIt == m_vecIt->end())
						{
							++m_vecIt;
							if (m_vecIt != m_endIt) m_buckIt = m_vecIt->begin();
						}
					}
					return *this;
				}

				ConstIterator operator ++ (int) // postfix
				{
					ConstIterator tmp(*this);
					++*this;
					return tmp;
				}

			protected:
				BucketVecIterator m_vecIt;
				BucketVecIterator m_endIt;
				BucketIterator    m_buckIt;

				friend class TLinearHashTable;
			};

			class Iterator: public ConstIterator
			{
			public:
				Iterator()
				{
				}

				Iterator(const BucketVecIterator& vecIt, const BucketVecIterator& endIt, const BucketIterator& buckIt):
				ConstIterator(vecIt, endIt, buckIt)
				{
				}

				Iterator(const Iterator& it):
				ConstIterator(it)
				{
				}

				Iterator& operator = (const Iterator& it)
				{
					Iterator tmp(it);
					swap(tmp);
					return *this;
				}

				void swap(Iterator& it)
				{
					ConstIterator::swap(it);
				}

				typename Bucket::value_type& operator * ()
				{
					return *this->m_buckIt;
				}

				const typename Bucket::value_type& operator * () const
				{
					return *this->m_buckIt;
				}

				typename Bucket::value_type* operator -> ()
				{
					return &*this->m_buckIt;
				}

				const typename Bucket::value_type* operator -> () const
				{
					return &*this->m_buckIt;
				}

				Iterator& operator ++ () // prefix
				{
					ConstIterator::operator ++ ();
					return *this;
				}

				Iterator operator ++ (int) // postfix
				{
					Iterator tmp(*this);
					++*this;
					return tmp;
				}

				friend class TLinearHashTable;
			};

			TLinearHashTable(std::size_t initialReserve = 64): 
			n_split(0),
			m_front(1),
			m_size(0)
			{
				n_buckets.reserve(calcSize(initialReserve));
				n_buckets.push_back(Bucket());
			}

			TLinearHashTable(const TLinearHashTable& table):
			n_buckets(table.n_buckets),
			n_split(table.n_split),
			m_front(table.m_front),
			m_size(table.m_size)
			{
			}

			~TLinearHashTable()
			{
			}

			TLinearHashTable& operator = (const TLinearHashTable& table)
			{
				TLinearHashTable tmp(table);
				swap(tmp);
				return *this;
			}

			void swap(TLinearHashTable& table)
			{
				using std::swap;
				swap(n_buckets, table.n_buckets);
				swap(n_split, table.n_split);
				swap(m_front, table.m_front);
				swap(m_size, table.m_size);
			}

			ConstIterator begin() const
			{
				BucketVecIterator it(n_buckets.begin());
				BucketVecIterator end(n_buckets.end());
				while (it != end && it->empty())
				{
					++it;
				}
				if (it == end)
					return this->end();
				else
					return ConstIterator(it, end, it->begin());
			}

			ConstIterator end() const
			{
				return ConstIterator(n_buckets.end(), n_buckets.end(), n_buckets.front().end());
			}

			Iterator begin()
			{
				BucketVecIterator it(n_buckets.begin());
				BucketVecIterator end(n_buckets.end());
				while (it != end && it->empty())
				{
					++it;
				}
				if (it == end)
					return this->end();
				else
					return Iterator(it, end, it->begin());
			}

			Iterator end()
			{
				return Iterator(n_buckets.end(), n_buckets.end(), n_buckets.front().end());
			}

			ConstIterator find(const Value& value) const
			{
				std::size_t addr = bucketAddress(value);
				BucketVecIterator it(n_buckets.begin() + addr);
				BucketIterator buckIt(std::find(it->begin(), it->end(), value));
				if (buckIt != it->end())
					return ConstIterator(it, n_buckets.end(), buckIt);
				else
					return end();
			}

			Iterator find(const Value& value)
			{
				std::size_t addr = bucketAddress(value);
				BucketVecIterator it(n_buckets.begin() + addr);
				BucketIterator buckIt(std::find(it->begin(), it->end(), value));
				if (buckIt != it->end())
					return Iterator(it, n_buckets.end(), buckIt);
				else
					return end();
			}

			std::size_t count(const Value& value) const
			{
				return find(value) != end() ? 1 : 0;
			}

			std::pair<Iterator, bool> insert(const Value& value)
			{
				std::size_t hash = m_hash(value);
				std::size_t addr = bucketAddressForHash(hash);
				BucketVecIterator it(n_buckets.begin() + addr);
				BucketIterator buckIt(std::find(it->begin(), it->end(), value));
				if (buckIt == it->end())
				{
					split();
					addr = bucketAddressForHash(hash);
					it = n_buckets.begin() + addr;
					buckIt = it->insert(it->end(), value);
					++m_size;
					return std::make_pair(Iterator(it, n_buckets.end(), buckIt), true);
				}
				else
				{
					return std::make_pair(Iterator(it, n_buckets.end(), buckIt), false);
				}
			}

			void erase(Iterator it)
			{
				if (it != end())
				{
					it.m_vecIt->erase(it.m_buckIt);
					--m_size;
					merge();
				}
			}

			void erase(const Value& value)
			{
				Iterator it = find(value);
				erase(it);
			}

			void clear()
			{
				TLinearHashTable empty;
				swap(empty);
			}

			std::size_t size() const
			{
				return m_size;
			}

			bool empty() const
			{
				return m_size == 0;
			}

			std::size_t buckets() const
			{
				return n_buckets.size();
			}

		protected:
			std::size_t bucketAddress(const Value& value) const
			{
				std::size_t n = m_hash(value);
				if (n % m_front >= n_split)
					return n % m_front;
				else
					return n % (2*m_front);
			}

			std::size_t bucketAddressForHash(std::size_t hash)
			{
				if (hash % m_front >= n_split)
					return hash % m_front;
				else
					return hash % (2*m_front);
			}

			void split()
			{
				if (n_split == m_front)
				{
					n_split = 0;
					m_front *= 2;
					n_buckets.reserve(m_front*2);
				}
				Bucket tmp;
				n_buckets.push_back(tmp);
				n_buckets[n_split].swap(tmp);
				++n_split;
				for (BucketIterator it = tmp.begin(); it != tmp.end(); ++it)
				{
					using std::swap;
					std::size_t addr = bucketAddress(*it);
					n_buckets[addr].push_back(Value());
					swap(*it, n_buckets[addr].back());
				}
			}

			void merge()
			{
				if (n_split == 0)
				{
					m_front /= 2;
					n_split = m_front;
				}
				--n_split;
				Bucket tmp;
				tmp.swap(n_buckets.back());
				n_buckets.pop_back();
				for (BucketIterator it = tmp.begin(); it != tmp.end(); ++it)
				{
					using std::swap;
					std::size_t addr = bucketAddress(*it);
					n_buckets[addr].push_back(Value());
					swap(*it, n_buckets[addr].back());
				}
			}

			static std::size_t calcSize(std::size_t initialSize)
			{
				std::size_t size = 32;
				while (size < initialSize) size *= 2;
				return size;
			}

		private:
			mutable BucketVec n_buckets;
			std::size_t n_split;
			std::size_t m_front;
			std::size_t m_size;
			HashFunc    m_hash;
		};

	}//end of namespace hash
}//end of namespace JHCPP
